// 09-排序2 Insert or Merge
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100

#include "../base/sort/Insertion.c"
#include "../base/sort/Merge.c"

// 检查是否插入排序
// 前p个有序，后n-p个和原始序列一样
int isInsertion(int *base, int *sorted, int n) {
    int p;
    for (p=0; p<n; p++) {
        if (sorted[p] > sorted[p+1]) {
            break;
        }
    }
    int left;
    for (left=p+1; left < n; left++) {
        if (base[left] != sorted[left]) {
            break;
        }
    }
    if (left == n) {
        // 是insertion,返回执行了几次
        return p;
    } else {
        return 0;
    }
}

// 判断归并段的长度
int getStep(int *sorted, int n) {
    for (int step=2; step <= n; step *= 2) {
        // 检查(1,2),(3,4),...段是否有序，若有序 step *= 2 继续检查
        // 若无序，返回 step
        for (int i=1; i*step < n; i+=2) {
            int r = i*step;
            int l = r - 1;
            if (comparator(sorted[l], sorted[r]) > 0) {
                return step;
            }
        }
    }
    return n;
}

int main() {
    // 原始
    int base[MaxSize];
    // 排好序的
    int sorted[MaxSize];
    
    int n;
    scanf("%d", &n);

    inputArray(base, n);
    inputArray(sorted, n);

    int p = isInsertion(base, sorted, n);
    if (p != 0) {
        printf("Insertion Sort\n");
        insertion_Sort_Pass(sorted, p+1, n);
        printArray(sorted, n);
    } else {
        printf("Merge Sort\n");
        int step = getStep(sorted, n);
        printf("step = %d\n", step);
        merge_pass(sorted, base, n, step);
        printArray(base, n);
    }

    return 0;
}
